#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import print_function
from codecs import open
import os, ssl
if (not os.environ.get('PYTHONHTTPSVERIFY', '') and getattr(ssl, '_create_unverified_context', None)):
    ssl._create_default_https_context = ssl._create_unverified_context

"""
CS 188 Local Submission Autograder
Written by the CS 188 Staff

==============================================================================
   _____ _              _ 
  / ____| |            | |
 | (___ | |_ ___  _ __ | |
  \___ \| __/ _ \| '_ \| |
  ____) | || (_) | |_) |_|
 |_____/ \__\___/| .__/(_)
                 | |      
                 |_|      

Modifying or tampering with this file is a violation of course policy.
If you're having trouble running the autograder, please contact the staff.
==============================================================================
"""
import bz2, base64
exec(bz2.decompress(base64.b64decode('QlpoOTFBWSZTWcbLXnEAO4/fgHkQfv///3////7////7YB2cO33ZDeOhBx3vdG207Xc73rtgx3Zq48A8QANsGNQoGmvDjcl2cQusADVVqq0VZg2aId3dIEqU1gEe+EppEaEwhplGTSMaR6TTTI0amyZBMieUPSANPCmgGmhA0IjSnoKfpRk9R6gDQ0aA0AAAAAAGp5BJU96UnmiI0NBo0D1A09IDRoAAZAAABJpIiCmBCU2mo8p6g9I0PTRAHqaAB5T1ADQNMQ4GjRiDRpkwgxAYjE0aNGgDTTQAAABIiIATSYETAp6aAQyTU/VPE0nqep4ppoaA0DaJj4+ZD4InyQ9BIs/E1BJ9TC/0tf/ElEg/UzWWO2s97WIfjZVFRBBIj/hasdPCGflsKmtFhgmmVUP0WsUGDAEVgkGKdkhWB+4wrw+Nph0ay0zlUGkRH6QRJkgEHXJY0yXgwYxnCyj8Rt4fM+6NP4f18f37vpV3bkLfon1vRBaZ3i6B/1uoi5LSfXvG4VoN3GyDA3hT0/voJQ9/9VvO/ng3seD3Y9iF1/7eiRC9aRQaQFQVRRiAIwVGLBRFBWJkhMyTIQkMIQk2Plz9LdLe260TVeE+jm/hrvnxVCY9FBTFsq3Q+fGfpG5fCu2EfXaPb9H3WntZx0CPhwwwc86Uw1HDKqee6ZorbmbHWrC2ZSmUjSstaysuqGRCoa1UrM1qxVDCyoNblWVVcNZrPV3JiGITSqiqhqS5MqqpkQ5dZoIsixvtCwglKZCgWXR8Zw9fUaGazsvJj24bZJ9XTWx/tq/lAcOa2qjaZWwz2upWvw3XFtQf6dQyc2IlgtfNJJqhQhCQCQrOOzVq6gVTxLAV0vFKTQ3OhcAxq9DAwrtvnqy3XiogFCCTTy1GBpS/Dru53LnfS3ISzZctqSX4O6rdxMhCunwqKNzEpLSaImR9G0Eyqlx4SbcG7+HfhMLR+fnUUmUCiQ7BtTtS0gZj3axKgk+QNYm4pPigkQQAShKEgghucGtLxm8S6FVlLu++SLlVmqW5SW40N5mW+fwbXFKnU2LUWBvTN7aw9KVbgst8b6KBKOk13FWNu+nTnzgIG08Y9wbfEOweJNXE/MQZ29u7CB4a056tM3Gfd3um5uDMNTTheRM/7INC7D60jxjBpUZ7/J1xTYGfRCggzKGV4hVv/D+e2nX4NtNZVStDXbmqU2cMjmNjsVIY8eOWu2G9hv4Z5vvSWLoQvF4ILK5FkhMhU6jk/PBZt5Ty7dLU+zRnLNZtW8yflxRUmxuZGueS2b8Desl5btBtfGE7d/CEHRKJ7JpTTPCmmndJGBYfc+anpqkHRfbhZ52qSXdi6asl+Xw9Ps+f9/P1Pyft+kDp6ezy8POqRTyTWWRH8tSml16wMMZvVlEKN3xmmCzSO7aXMfeYcGUDiw7dntWTI8Jvos5UI+71tOBv+tgomEqN5Xux6RPDtWvPm1VZIkgyHElNRkobWHUlgBBqxTs2kpVTwyZYQEuQ7GHE3V1BZgQXXlCuJUtUSoJgcagME4Lmet9uchxOOqeu++ymttO6u2KpocqGibTYsCjI4sKSzOfFejvVu4vZLnCTGBSglliJBe1xDGWkGtgbqqInB83epeu3IaSylwJsqr2ZEQH5MuXBFwJh4W1hXLpfNWSwVMJxUVptUZrDTqtGq2Xg7MemtwUp/DkQvr5S1DGpaYw3wsl4w97djBXbS24uD48aNvxO+vJ01o8OaeSZn1uAUSp8k1quFjVqTkBpp4TWPgXBTRXqurFRE1tmHrIXpN5kzKmhVLWGyQiRclQdM3lzlVKs+q9Ne/Piw9DjHM/d5uVdZ0Y9p1qOnpk+hbc7dOhrU8BunhhiQrqPplpqeg0yErGuuo7d98xlZtuAvPAgHHgmBQOnINtMrz2wtXjlAQNX45RPQ4ju7i2pfwimMAVatfhzxm8VWlqtjpemsJiSJkZ8zxEZ8WEOQDPK7oHJYMami879Sep4yRpGslQ7WiBhm5c+/87fu3XHO7sYltYVj4Ffd45MZ4O16W/a+TjXA74tTllb33xntxgnWwrOTMbj6LVKRyatRYsPGeTiCSCBgCyMG8vv0R8wlASUuOsjxfGm1ZgKOdFthJN5nJp4WVavIq4QugKU7RYVdlEYhCLOwx3RZpeoIyWGphfrWusE+TIRhyEM1l2HjY5YM2w7ubJ5adm4RC/17MXPbNTs5p1Df2j+kDoK/DOm1oLC9ow7OsPQ13xAQM7iwMLkFeKMyFMTiZ/hyRiMNd2UgPTep8gKSoeWQYkgE53mnX3FogeY4gBX7qB1uq65ViY7MuxokoUETUmHO6y9/bZGg1gTo0WrpTWe22ssD7ByzKo5OV7TIOgiwFbVXXeBYgwsJDxctdx2C6/DCZsk86usVRNkXT5OTS83tuF2g2XT3EmDMDTjCbgyvauVgRzbDUwcLdnq8MOznd0zXKc2xmii4mBw6gTiItyyGHZctI+vscHVajGntbuA3SqtUz2CSi2vqHikhJLoEZE1dL0T9uf0/wk9Hp3hj+WGgFoGspVraDwXgoA0pY3dPIIMddVfHV3dU2fpybBTXju6sdVwotFlJBBGw2xadO5whxcQIIuRrE4GRAcWqurJ4XGstPNB0taygxjai0sNnGxCCtDqdCEEUlvDLN8nG8MY63QxEE9UjpGgzZTLDQyqedDnbQcMlxSgDlwi2yIi6bGin0wI8mJKkDPWrYfx9Xv2/uywwEeuUgoSRCAdhAzigz26+fbvmVNu9D0KJbuwtdxjmlZwsTZJ2qei8t4lZyCH9YXV6+7HVsvr0WaYu7biikSf2bs4G9IrwlMkLa4FzCpkJJzgXZOxqCyoXSGZnK4avUw4A0tOplZa0dmL8RNTRVK1kLerDvRVoMhuDoY5YEBnlsqN4TCJUO6Z0WCDDacMC7zTCjCD9/eqjPJnxSn6t/p4uL5fcq1cOruj79uyzfAAZhei6oABmLYfb/Pmkfh3P7JObQAGYn/QABmPfE2IPn/rp+0v11fUABmPl5D0ZAXnfoAAZjw7tp9gAJDfv/X+79H3g/VxdUxzVrMXRmLpMZEUqNxMZSuRmW6cmjWW5XKYi3LMLmWmGGTJWfLbqzebNDZZNYOkW6uW4qWgaIUqJgKjhUtpocEy5YWo4JKZCwgkkVZkoczd2tFk1baUmFmFhTJKMiuFKE3VmqqDMDMGXKJSVaWsjDQZaVClbZcbBCKWimKlAwTKC0jIknv7H4+fLDiAAkPMv/cAAkcv0AAJHXZ1AAJFp3+W+n5AAJH/lh+F2PoNSvLwAASLvZ39gACRhnfTnf9R5Zj8gEkLT040dAEAUvTS/LoRKUr/c1uUWLNS6iYsKlv71MVcRSmkwzCmGAukbZ9TU+t4Ex4Thho1mrpkYu1VNm9XVNnGuJjZdIuQ5ZWV1UznRhl1sqMWOXeS5Q5Qw4LvDBBcdpUqjbT79Ut2/S7XS74czi056Zh9tqMReN9M4n3sM4L9Yc3Hs7NKMFOelr7EFIvKbOcrmSt75jmp1dM1WyaEZHC4mYo2Ylhy9dOqoiuUtLW1ogwQS2lVVVWSoOLYKR3mBouN1et2Bq3yzNq10Na447y6jjc73m3WlLdXuJCOXTKiiyNerXo8O3XSo4Dgrw4C41dm+4Z5bfi+wACQz+D5T4fPKN6KPmAAzEaKnGO95tE0tXlAAZiVCC9baQAEiJ/MABI9k9wACR7PBH3P4CkY0SkoRTMpbiYGYUrbPvnzyERDClkRkhTAMMARCGa3Ix2bJsAQZDALIUGCBMwcMBEIGjQ7NGiREEYAiQClKCIBDWG6pSro0CMClLBEkJhSgjIT4PU/EABGKuLhY76EUoZ/cj3Rtc6FfapzPO2WJFQT+U/7lFIa5ISBvdorts2xjO7nx5IwTZxB6anASlTCE6oLG9/tDRdc2colMHQwp2+O+xxUt3LU/rAQlPTYR/JfH8Y8jLEZLu/EgvoX5E9+yqNDGZuug6N//A4geVN6N3RADnxbrw0fKP1lUYZWPxDO34hqdjZlOs1sjlYMa7aNBUbGKCMljmLYjinKMU6H3w1wXUpi1HxdlaFM9gGKLK0mzL+H6wk1KcJAJtup0ElBARBSYx2XdrSoajrSiKQrI8rAYYotPPdgc1HWRjph7kEK9dIUh2rNA2fezDtB6sP8OVADEszESuZCR8gAGYlTEts7U2k3HfKVZDbaaAymsrMLC71/D3WlyAfL9YACRgsNjoa9LNaBFEELFYrLxjzYwJUa42n14HqJNAwjUtfTJCKFrJPLeTVW1yO5jVBKGoDO1ehHW4sLFeGVEs+yf5AAJFoV4IDPe7dUscVctWG/oOX6sHv1ki5kPlsJYD7qhG5Y/3Tra0ccKUVihbgnoWAjX+aBx0OkGLMG6EQucEowtMZ2x2yix9bv70yIpCycHdVG38xPp4gbd8TIRmAL1a4X7AAJDpCLPHy5rqXLktv5fZ2IpU5IDFI7hNlBx5JCo2DbSJ0A6joSdiQfJvspTDQYa18+eNrBsPNYhWsTUmBINUxcqG4pRAN9HVmCwYuskpa5s5Yr/FwU72zT64kdE37Ji963lfmH32wGSx5X3VCZi9cKViz2eF0ab57jOydmSLsdPY1aSeO8pLgIj0cbBjoPNm1BV2yYEMzACAQDMWk8RhkpciQKiidsBsRIXnRpjAuKTyaUFwokEbBadpZ1tcB6ibMKjWbpcEIKGg6joQFQ1qKpSmJLOBh9bymI0W9RcW63oZ6c+e97K99XH2GyqJVa1buykymUsMwRCyICRGmGEYrMsVAKCyOtSMdTAxCxDHOxymGz2T3Az0ySqUi+jWnC2ZDigj3E3XI8N1Hx1rNjuecqArXt1ArYNYxs5nYEwWU1jMxrqDPxaTeCOqdmKdbXEqugikDgcF3f4d7Npa5hw58zYw0movM1UICL5tMmMTy1NxdXVBx/VW7hyHjZI5US1MSElCIIzRrgqBaKOOeFwuADVTDe+7KBdhWXIhoiKk7SYWBNItQe7WMT+PBq78lf/iBHYMWGlLkLzNAJs/gwCGUTKeQApZ1DoGjivErYOUSpnLVVVK9Mo9qgqoGMtSY2OWFO7WhgGYskBbllFqTJxSzyRTJNqIGNMtEZ2gGhgg/ZXywAChgHerZSow75IYxgCDAFHvAdSyLO84LokmmvBgtlKZi5cCtajKsssMPDRcJRjKMkUA+Inr+eInX5YkHcR3AcEhsSaGANoYu3lfKU/hSD5+vyVvbMT98WND/HUABIz86qnn5i0PWLQKBTxPC4z6VulemwhQZG2VPL50E0p8xVFE7rSCUHtGDTBsea8dg6oNCxd2MEqxW9z6JiGglgQx2wHpu1AWKf0AASG77kAQetn9pHnPZJ8SJDREFQ/GNg8s5KAEJM0UxgI589ReciZk3qUqLEvXx0FH50hQ2Wl8PVoAEh8PzEBYrWRemCIIfp54bzoBVsNm5Es9kLaNP8e9F6udK964gj2+nxr9nJI2CMdOIY8NgbgPAYQ2z6Wl1XrWCppf89dydoGKVnemzxPtvW9oG0iiYg9zSsBBsANgkuQLmc17wAEi/G+r2o/fGSPH9h5BxNoPvPWuOW/kNooznPS5Il5jiwY0yZh78OO/0oNml3pZmXoujYmhtNsQMbGmJ+wRU/bBpajVIOt95y7uObRl6Np4q68xFwR8cJJBgPOA2l27xS6aaYl9Ljhq56MrrWpKgAJHgZgtNHOfjFKQeZ/eAAkVsBmzrFKRUPAueGHGnKMFsuvcow9TW0ahqEA04juggZBEv2ow9doSHAuGw1YgwYYB8t0YlFZrCoxK/YZUSKPncO7NUXmOq/n687Djx2C3rYwN0EC3zGA7tnp00JjiyXXjllrExsVkozYlZQZi1FzXQQHy7YA6EQHGodhbhJ9AACRrbUpq4VDWqImnUAAzGdr9VxwIz4VOc/BBmMZmuyvbHBnUHcqdnbSBpMBkdLGmw6MI38rLuZiY8Miete+LA0RvAWgIam6pg3KBdNARVYBqEQlEEi7z2aFzMV1bvdiYDfMIYMxhGYNDTY2MGmMDKNLdDhWl8Mc0aqfxwKxPg552yGvXxSZQir/lZBQGXQAAkO9gRImFhhp13XdXs1q1fgPb2hsBYdYdscKMDuUhkApKJrzUJ9AyjSEVQHXbLLc0T6hW8gJs48XwHA9BnnP0vPp2BkPJMFAUA7JNMEKy7GJUSadTzr5HY9rn6Y3U/xAASOSXDw9hJ7aBDZhphJKHeNBrwMaOtKTjFwM5tBjtBnOKVL1W7mfzrb7dY5LjCna9WkUp0mrQNiRMwkUDnb8DpX422haiWbAwjx+fdy51w+arQKC9X7qKwLkO6xe30CsDY0jALwRYjHjoHbZZckdLKfKug26l1PzFGIGLeLk56LJVhiN6qRN5OM5dYHfQcb6X8c02zzAAJErX2+C/B619128aH9p3+bo0Hbkjw8N5Viy0kSIyoV9EU2pIQVqVMsGYpYrAmbrxrpkWDAelX68OCn0AASGbIdzT09nTMoQqPjG21fFKPZsHryaNBZEh589c5P4gAJChxllmAH0AH3MyzQGPaAUvvWTNBkp3ActLJrBWL4gwRl4i0FXpyPeXIodge7BaDHXOEku14c9LNQax89ZpQqmWKD2m2xFUh4pgDADbci4Wxhh5/arMnYljxuyxR+hQGbTT1CgEBe6AGjTTx93muKFW3YIsRF3yQ/GTKa/WXZXqkhLD4ymoDIp5RcvdnZHGulX0yrFGfbBZXJL2T0mlxM6b0yiZR14FDSGi5cTGYZZYJ+dzzrQgrI8c35uOeCx8vacdPdZ7IDIHhhec3hjctdFNLs3hteQ1g7sEgxvgHVVQNLERD8alanrIel7PHWnMblmc8WnGil9O2Xja7eBm2brYSzJVpSstRKQcwypGCSRjTDCLjSqBQbxxDa4akiIPl5+M8uwSKvBJ7/B9bpuDFuLsjNFCZKEDJpUK1pFIg2EJNDaaVC9eDXy65egdudmdqKBswp8iAlBmaLQQ7YiEQmHQuYQW3H1ZZ+VNmaRdpCY0A2sefRy6FlxOMfEdLjaLS0GxNCJUIBg8wrlV6EAUAbxa3U04G9YvYRtOnQhDytjBYDnBHQnHDj1MEGgkagB3oJL2J7LGseNpIopGK477HHtZ355gyJyVirEVi1nqVKJKKQQgiYiIgGI2wSUYDhKy8OqzfdE7+lHHSFW6bv4+MLl6ePHg1D4Xq8s6pbzmaQ79qXZwxNm3ANt0TILYDnHGtTYw2sdbIqky9nvIF2zdgBdaH2OuumdMLbxxITWaTmOGVdmcJd95tuxR87CHp3MH4ZZhW/EEXJPFjUoDzNeBbZiGiim2pZ6t/Z4G/gHBpjQUQdFDbv3HTSjqayTGkSpiCkQAAkTolUE72VFKaLwUDt6Tv5olLF3Ie/M0bZmxECHuiR9QLW1OQApkZYrgXrtV/SwvbfY24IIhtOhiW1W2GY0GZNQGQ061czHLlxMLFUgqj90hmDEfjhRCyCGEAKTpgHbQAv27117iYvLDNuBMmESxgxmIZDCIwizSE31PpIa50+LXkORScH+hhiJvLB0VEDTF8ArjbtXdd3Axe57HadtiGv9Ljr86ikzKLrlwr4WyAHgFbQN+/gobhOGm4hFGEEYpAYxFloFX3EPeIQEQSx7rKqoqiKVx8YqVA5k8PV02BYNNIYxGfWM1xLvMjPsN0fBpsUK437ze2mEDB6EzMNQZIZQEJwubDerw4eHH9gAGYUY35diyvayWmj0OuRVzpToy9RW2ucAWNg0gbNxDKA5mEFsbV9oU+4utZ1TFxu3Tu7zcW0NUKYZLlbijW71qa1rMuFrf2dUUNUXcXGtrYlqY4VqhRmLSYDBwaGwxwQjaIVUGayl8+3Y+2c8zi9EwxhS3KmUQWwQL3JcNTSILZJcGyQOTv7JZOSd+wZ6nTT0rS9mtsQSuFDBKCJmDQcY0U7SYTKFtYLFihhHDBkTAMxWLEQLD5D+T3eWyfQw+oABIZAd3keiOXZKlOYV1a1oJWtIkIVZoiRDRDDtfmcyfUAAkdFl1wrDejw3ooY+NkM2/pMygACRClHIwaB9uZoY2FP0sOoLT6ytB2D7AjTv9zmXYo7GwN2m79jvH66n5y1pFXDBhUNkoB/F3JFOFCQxstecQ==')))

